package lt406

import "sort"

/*
406. 根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。
每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。
返回的队列应该格式化为数组 queue ，
其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
*/
/*
首先找ki=0的，然后根据身高排序
然后找ki= len(ki==0)的，根据身高排序
h升序  k降序

然后遍历，如果当前是剩余未安排里面最矮的，则k值标识他在“剩余空位”的索引，如果多人h像糖，按k值从大到小取
[ 0, 1, 2, 3, 4, 5 ] [ 4, 4 ] 4
[ 0, 1, 2, 3, 5 ]    [ 5, 2 ] 2  只有两个位置
[ 0, 1, 3, 5 ]       [ 5, 0 ] 0
[ 1, 3, 5 ]          [ 6, 1 ] 3
[ 1, 5 ]             [ 7, 1 ] 5
[ 1 ]                [ 7, 0 ] 1
[ [ 5, 0 ], [ 7, 0 ], [ 5, 2 ], [ 6, 1 ], [ 4, 4 ], [ 7, 1 ] ]
方法一：从低到高考虑
思路与算法

当每个人的身高都不相同时，如果我们将他们按照身高从小到大进行排序，
那么就可以很方便地还原出原始的队列了。

为了叙述方便，我们设人数为 n，在进行排序后，它们的身高依次为h 0,h1,⋯,hn−1，
且排在第 i 个人前面身高大于 h_i的人数为 k_i。
如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 i 个人时：
	第0,⋯,i−1 个人已经在队列中被安排了位置，并且他们无论站在哪里，对第 i 个人都没有任何影响，
		因为他们都比第 i 个人矮；
	而第i+1,⋯,n−1 个人还没有被放入队列中，但他们只要站在第 i 个人的前面，
		就会对第 i 个人产生影响，因为他们都比第 i 个人高。

如果我们在初始时建立一个包含 n 个位置的空队列，而我们每次将一个人放入队列中时，
会将一个「空」位置变成「满」位置，那么当我们放入第 i 个人时，
我们需要给他安排一个「空」位置，并且这个「空」位置前面恰好还有ki个「空」位置，
用来安排给后面身高更高的人。
也就是说，第 i 个人的位置，就是队列中从左往右数第ki+1 个「空」位置。

*/
func reconstructQueue(people [][]int) [][]int {
    sort.Slice(people, func(i, j int) bool {
        a, b := people[i], people[j]
        return a[0] < b[0] || a[0] == b[0] && a[1] > b[1]
    })
    ans := make([][]int, len(people))
    for _, person := range people {
        spaces := person[1] + 1
        for i := range ans {
            if ans[i] == nil {
                spaces--
                if spaces == 0 {
                    ans[i] = person
                    break
                }
            }
        }
    }
    return ans
}
